/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-24
 * Time: 23:18
 */


public class Solution {
    //转换为链表是否带环的问题
    public int findDuplicate(int[] nums) {
        //快慢指针
        int fast=0;
        int slow=0;
        int length=nums.length;
        //先寻找相遇节点
        while(fast>=0&&fast<length&&slow>=0&&slow<length){
            fast=nums[nums[fast]];
            slow=nums[slow];
            if(fast==slow){
                break;
            }
        }
        if(fast<0||fast>=length||slow<0||slow>=length){
            //没有环
            return -1;
        }
        //开始寻找入口节点
        int begin1=0;
        int begin2=fast;
        while(begin1!=begin2){
            begin1=nums[begin1];
            begin2=nums[begin2];
        }
        return begin1;
    }
}
